package com.leetcode.bit;

/**
 * @author Dennis Li
 * @date 2020/7/21 16:09
 */
public class SingleNumber2_260 {

    public int[] singleNumber(int[] nums) {
        int ret = 0;
        for (int num : nums) {
            ret ^= num;
        }
        // 异或后的最高位一定不相等
        ret = Integer.highestOneBit(ret);
        int[] ans = new int[2];
        for (int num : nums) {
            // 通过这个不同的位置，对数组进行了拆分
            if((ret & num) == 0)
                ans[0] ^= num;
            // 拆分后的两个数组各含 n / 2个元素。且必定各包含这两个不同的元素
            else
                ans[1] ^= num;
        }
        return ans;
    }

}
